//--------------------------------------------------------------------------------------------------
//                                                   ___  __  __  __  __  __  __  __    __  __  ___ 
// Copyright 2010, Koert van der Veer.              / __)(  )(  )(  \/  )(  )(  )(  )  (  )(  )/ __)
// Licensed under the Apache License,              ( (__  )(__)(  )    (  )(__)(  )(__  )(__)( \__ \
// version 2.0; ("the License")                     \___)(______)(_/\/\_)(______)(____)(______)(___/

// You may not use this file except in compliance with the License.
// You may obtain a copy of the License at 
//     http://www.apache.org/licenses/LICENSE-2.0 
//
// Unless required by applicable law or agreed to in writing, software distributed under the License
// is distributed on an "AS IS" BASIS,  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
// or implied. See the License for the specific language governing permissions and limitations under
// the License. 
//--------------------------------------------------------------------------------------------------
// This file is part of cumulus,  an memory manager implementation in C++.  Details are discussed in
// my blog,  which can be found at http://ondergetekende.nl.  Comments,  suggestions and bug reports
// are welcome. They can be added as comments at the blog. Be advised that in its current form, this
// code is most likely not production ready; it simply hasn't been tested sufficiently. 
//--------------------------------------------------------------------------------------------------
// Implementation of a static allocated TLS alternative. This is basicly a hashmap with the threadId
// as the key. Contrary to other TLS implementation, this implementation does not rely on dynamic
// memory allocation.
//--------------------------------------------------------------------------------------------------
 
#pragma once

#include <windows.h> // for InterlockedCompareExchange

namespace Cumulus
{
namespace Utils
{
template< typename Type, int ThreadCount = 30 >
class FakeThreadLocalStorage : public NonAssignable
{
public:
	FakeThreadLocalStorage();

	// Accessors for the data
	Type* operator->();
	Type* operator*();

	// Returns true if TLS is available for the current thread
	bool IsAvailable() const;

	// Iterator for the TLS entries. 
	// This iterator in itself is thread-safe, but accessing TLS data outside the correct thread
	// obviously isn't.
	class Iterator
	{
	public:
		Iterator( FakeThreadLocalStorage< Type, ThreadCount >& inTLS );

		// Returns true if we iterated past the last TLS entry.
		bool IsAtEnd() { return Idx >= ThreadCount; }
		// Returns true of we iterated backward past the first TLS entry.
		bool IsAtStart() { return Idx == 0; }

		// Returns the threadId for the current entry.
		DWORD GetThreadId() { return TLS.Entries[Idx].ThreadId; }

		// Data access operators
		const Type* operator->() const { return &GetCurrent(); }
		const Type& operator*() const { return GetCurrent(); }
		operator const Type*() const { return &GetCurrent(); }

		Type* operator->() { return &GetCurrent(); }
		Type& operator*() { return GetCurrent(); }
		operator Type*() { return &GetCurrent(); }

		// Increment operators
		Iterator& operator++() { IterateNext(); return *this; }
		Iterator operator++(int) { Iterator Backup(*this); IterateNext(); return Backup; }
		Iterator& operator--() { IteratePrev(); return *this; }
		Iterator operator--(int) { Iterator Backup(*this); IteratePrev(); return Backup; }

	private:
		int Idx;
		FakeThreadLocalStorage< Type, ThreadCount >& TLS;

		void IterateNext();
		void IteratePrev();
		Type& GetCurrent() { return TLS.Entries[Idx].TLSData; }
		const Type& GetCurrent() const { return TLS.Entries[Idx].TLSData; }
	};

private:
	struct ThreadLocalStorageEntry
	{
		Type TLSData;
		mutable volatile LONG ThreadId;
	};

	ThreadLocalStorageEntry Entries[ ThreadCount ];

	// Converts the current thread id to an index into the Entries array. This works like your 
	// typical hashmap. Interlocked primitives are used to make sure this code is thread safe.
	int GetThreadIndex() const;
	
};


template< typename Type, int ThreadCount >
FakeThreadLocalStorage< Type, ThreadCount >::FakeThreadLocalStorage()
{
	// Clean out the entries
	memset( &Entries, 0, sizeof( Entries ) );
}


template< typename Type, int ThreadCount >
Type* FakeThreadLocalStorage< Type, ThreadCount >::operator->() 
{
	int idx = GetThreadIndex();
	if( idx == -1 )
		return NULL;
	else
		return &Entries[idx].TLSData;
}

template< typename Type, int ThreadCount >
Type* FakeThreadLocalStorage< Type, ThreadCount >::operator*() 
{
	int idx = GetThreadIndex();
	if( idx == -1 )
		return NULL;
	else
		return &Entries[idx].TLSData;
}

// Returns true if TLS is available for the current thread
template< typename Type, int ThreadCount >
bool FakeThreadLocalStorage< Type, ThreadCount >::IsAvailable() const
{
	return GetThreadIndex() != -1;
}


template< typename Type, int ThreadCount >
int FakeThreadLocalStorage< Type, ThreadCount >::GetThreadIndex() const
{
	DWORD ThreadId = GetCurrentThreadId();
	assert( ThreadId != 0 );

	// cheap hash that works well for thread IDs
	int BaseIndex = (ThreadId + (ThreadId>>5)) % ThreadCount;

	for( int i=0; i<ThreadCount; i++ )
	{
		int Index = (BaseIndex + i) % ThreadCount;
		if( Entries[ Index ].ThreadId == ThreadId )
		{
			return Index;
		}
		else if( InterlockedCompareExchange( &Entries[ Index ].ThreadId, ThreadId, 0 ) == 0 )
		{
			return Index;
		}
	}

	return -1;
}

template< typename Type, int ThreadCount >
FakeThreadLocalStorage< Type, ThreadCount >::Iterator::Iterator( FakeThreadLocalStorage< Type, ThreadCount >& inTLS )
: TLS(inTLS)
, Idx( -1 )
{
	// Iterate to the first entry
	IterateNext();
}


template< typename Type, int ThreadCount >
void FakeThreadLocalStorage< Type, ThreadCount >::Iterator::IterateNext()
{
	if( Idx < ThreadCount )
		Idx++;

	// Iterate past empty slots
	while( Idx < ThreadCount && TLS.Entries[Idx].ThreadId == 0 )
	{
		Idx++;
	}
}

template< typename Type, int ThreadCount >
void FakeThreadLocalStorage< Type, ThreadCount >::Iterator::IteratePrev()
{
	if( Idx >= 0 )
		Idx--;

	// Iterate past empty slots
	while( Idx >= 0 && TLS.Entries[Idx].ThreadId == 0 )
	{
		Idx--;
	}
}
}
}